#ifndef GRAPH_H
#define GRAPH_H

#include <QtCore>

namespace sk {

enum VertexColor {
    WHITE, GRAY, BLACK
};

typedef int TTimestamp;
typedef int TDistnace;

template <class T> class Vertex;
template <class T> class Graph;
template <class T> class Edge;

template <class T>
class Vertex {
public:
    typedef Vertex<T> TVertex;
    typedef Edge<T> TEdge;
    typedef Graph<T> TGraph;

    friend class Graph<T>;

    Vertex(const T& value)
        : tValue(value)
        , vcColor(WHITE)
        , ts1(-1)
        , ts2(-1)
        , nDistance(-1)
        , bVisited(false) {}

private:
    T tValue;

    VertexColor vcColor;
    TTimestamp ts1, ts2;
    TDistnace nDistance;
    bool bVisited;

    QList<TEdge*> edges;
};

template <class T>
class Edge {
public:
    typedef Vertex<T> TVertex;
    typedef Edge<T> TEdge;
    typedef Graph<T> TGraph;

    friend class Graph<T>;

    Edge(TVertex* const from, TVertex* const to, int weight=1)
        : vFrom(from)
        , vTo(to)
        , iWeight(weight)
        , ts1(-1) {}

private:       
    TVertex* vFrom;
    TVertex* vTo;
    int iWeight;
    TTimestamp ts1;
};

template <class T>
class IGraph {
public:
    typedef Vertex<T> TVertex;
    typedef Edge<T> TEdge;
    typedef Graph<T> TGraph;

    virtual TVertex* addVertex(TVertex* const vertex) = 0;
    virtual TVertex* addVertex(TVertex* const from, TVertex* const vertex) = 0;
    virtual TVertex* findVertex(const T& value) const = 0;
    virtual TEdge* addEdge(TVertex* const from, TVertex* to) = 0;
};

template <class T>
class Graph : public IGraph<T>
{
public:
    typedef Vertex<T> TVertex;
    typedef Edge<T> TEdge;
    typedef Graph<T> TGraph;

    TVertex* addVertex(TVertex* const vertex) {
        vertices.append(vertex);
        return vertex;
    }

    TVertex* addVertex(TVertex* const from, TVertex* const vertex) {
        vertices.append(vertex);
        TEdge *e = new TEdge(from, vertex);
        from->edges.append(e);
        edges.append(e);
        return vertex;
    }

    TVertex* findVertex(const T& value) const {
        for (int i = 0; i < vertices.size(); i++) {
            TVertex* const v = vertices.at(i);
            if (v->tValue == value) {
                return v;
            }
        }
        return NULL;
    }

    TEdge* addEdge(TVertex* const from, TVertex* const to) {
        TEdge* edge = new TEdge(from, to);
        from->edges.append(edge);
        edges.append(edge);
        return edge;
    }

    int verticesCount() { return vertices.size(); }
    int edgesCount() { return edges.size(); }

    void debug_printVertices() {
        printf("Vertices: %d\n", vertices.size());
        for (int i = 0; i < vertices.size(); i++) {
            TVertex* v = vertices.at(i);
            printf("vertex %d (%d)\n", (*v).tValue, (int)v);

            int edgesCount = v->edges.size();
            for (int j = 0; j < edgesCount; j++) {
                TEdge* const e = v->edges.at(j);
                printf("  edge to %d\n", e->vTo->tValue);
            }
        }
    }

    void debug_printEdges() {
        printf("Edges: %d\n", edges.size());
        for (int i = 0; i < edges.size(); i++) {
            TEdge* const edge = edges.at(i);
            printf("edge from %d to %d\n", edge->vFrom->tValue, edge->vTo->tValue);
        }
    }

    void depthDirstSearch(Vertex* const v) {

    }

    void breadthFirstSearch(Vertex* const v) {
        QQueue<Vertex*> Q;
        Q.append(v);
    }

private:
    typedef QList<TVertex*> VertexList;
    typedef QList<TEdge*> EdgesList;

    VertexList vertices;
    EdgesList edges;
};

}

#endif // GRAPH_H
